class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = min(x, 46340) + 1
        while left+1 < right:
            mid = left + (right-left)//2
            if mid*mid <= x:
                left = mid
            else:
                right = mid
        return left